package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.回溯;

/**
 * @author By ZengPeng
 */
public class 力扣_79_单词搜索 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_79_单词搜索().exist(new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}},"C"));
        System.out.println(new 力扣_79_单词搜索().exist(new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}},"ABCESEEDASFC"));
        System.out.println(new 力扣_79_单词搜索().exist(new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}},"SEE"));
        System.out.println(new 力扣_79_单词搜索().exist(new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}},"CSEECSEE"));
        System.out.println(new 力扣_79_单词搜索().exist(new char[][]{{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}},"ABCB"));
    }

    /**
    题目：给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。
     如果 word 存在于网格中，返回 true ；否则，返回 false 。
     单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
     同一个单元格内的字母不允许被重复使用。

     示例 1：
     输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
     输出：true

     示例 2：
     输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
     输出：true

     示例 3：
     输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
     输出：false

    分析：【perfect】
       1.递归+回溯：先找到首字母，然后首字母前后左右查找，若不行继续遍历首字母  --执行用时：54 ms, 在所有 Java 提交中击败了98.13%的用户
         变量：当前再找的字符，已经用过的元素【还是得递归+回溯】
         优化：A.从后向前，剪切掉不需要的.  【单是如果结果很多都是后面的，找不到最前面的，这不一样吗？】 优化失败
               B.节省内存，在原始数组上操作 .【懒得记录上传的字母了】 boolean记录更清晰，优化失败
               C.代码可以优化一下，太多了，写在下次循环判断会更好  --执行用时：104 ms, 在所有 Java 提交中击败了53.06%的用户
               D.遍历前，先判断几种直接不符合情况   --执行用时：0 ms   牛逼

    边界值 & 注意点：
       1.
     **/
    public boolean exist(char[][] board, String word) {
        boolean[][]  useed = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if(board[i][j]==word.charAt(0)){ //找到目标字符时，才会左右找周围的数据
                    if(recurtion(board,useed,word,0,i,j)) return true;
                }
            }
        }
        return false;
    }

    /**
    *  回溯：数组记录元素是否被使用
    * @param  board 单词表
    * @param  useed 数组记录元素是否被使用,防止多次使用
    * @param  word 单词
    * @param  index 正在找的下标
    * @param  currRow 当前下标row
    * @param  currColumn 当前下标column
    **/
    private boolean recurtion(char[][] board, boolean[][] useed, String word,
                              int index, int currRow,int currColumn) {
        if(index==word.length()) return true;
        if(currRow<0 || currColumn<0 || currRow>board.length-1 || currColumn>board[0].length-1) return false;//这里判断变多了，浪费时间
        if(board[currRow][currColumn]!=word.charAt(index) || useed[currRow][currColumn]) return false;
        useed[currRow][currColumn] =true;
        boolean res =  recurtion(board,useed,word,index+1,currRow-1,currColumn);//之前是相等，才有资格进入递归，可能是这里浪费时间了
        if(!res) res =  recurtion(board,useed,word,index+1,currRow+1,currColumn);
        if(!res) res =  recurtion(board,useed,word,index+1,currRow,currColumn-1);
        if(!res) res =  recurtion(board,useed,word,index+1,currRow,currColumn+1);
        useed[currRow][currColumn] =false;
        return res;
        /*if(currRow>0 && !useed[currRow-1][currColumn] && board[currRow-1][currColumn]==indexChar){//上
            useed[currRow-1][currColumn] = true;
            res = recurtion(board,useed,word,index+1,currRow-1,currColumn);
            useed[currRow-1][currColumn] = false;
        }

        if(!res&&currRow<board.length-1 && !useed[currRow+1][currColumn] && board[currRow+1][currColumn]==indexChar) {//下
            useed[currRow+ 1][currColumn ] = true;
            res = recurtion(board, useed, word, index + 1, currRow + 1, currColumn);
            useed[currRow + 1][currColumn] = false;
        }

        if(!res&&currColumn>0 && !useed[currRow][currColumn-1] && board[currRow][currColumn-1]==indexChar) {//左
            useed[currRow][currColumn -1] = true;
            res = recurtion(board, useed, word, index + 1, currRow, currColumn - 1);
            useed[currRow][currColumn -1] = false;
        }

        if(!res&&currColumn<board[0].length-1 && !useed[currRow][currColumn+1] && board[currRow][currColumn+1]==indexChar) {//右
            useed[currRow][currColumn +1] = true;
            res = recurtion(board, useed, word, index + 1, currRow, currColumn + 1);
            useed[currRow][currColumn +1] = false;
        }
          return res;
          */
    }
}
